package com.study.lu.链表;

import com.study.lu.链表.bean.Node;

import java.util.HashSet;
import java.util.Set;

public class LinkCycle {
    /**
     * 链表中是否存在环形结构
     * eg  1->2->3->4->2... 这种就存在环形结构
     *
     * @param args
     */
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.next = node2;
        Node node3 = new Node(3);
        node2.next = node3;
        Node node4 = new Node(4);
        node3.next = node4;
        Node node5 = new Node(5);
        node4.next = node5;
        Node node6 = new Node(6);
        node5.next = node6;
        //node6.next = node2;

        //  System.out.println(bf(node1));

        System.out.println(twoPoint(node1));
    }

    private static boolean twoPoint(Node node) {
        if (null == node || null == node.next) {
            return false;
        }
        Node slow = node;
        Node quick = node.next;
        // 如果慢指针追上了快指针说明一定存在重复节点
        while (slow != quick) {
            // 如果quick 都空了 那么说明走到了队尾，那么则说明不存在环
            if (null == quick || quick.next == null) {
                return false;
            } else {
                slow = slow.next;
                // 要保证 quick 走的比slow快，这样才能套圈
                // eg  在操场上跑步。假设都是恒定速度。那么慢的一定会被快的套圈。在套圈的时候，也就是两者相等的时候
                quick = quick.next.next;
            }

        }

        return true;

    }

    private static boolean bf(Node node) {
        Set<Node> set = new HashSet<>(16);
        while (null != node) {
            if (set.contains(node)) {
                return true;
            } else {
                set.add(node);
                node = node.next;
            }
        }

        return false;
    }


}

